This invention relates to a Booth's conversion circuit involving Booth's algorithm. Generally, Booth's conversion can be expressed by the following theoretical formula: EQU QB=N.sym.(QX.multidot.X.sub.i +Q2X.multidot.X.sub.i-1) (1)
where:
QB=a converted value, PA1 N=logic 1 or logic 0, PA1 QX, Q2X=the logic values of multipliers, represented by logic 1 or logic 0 PA1 X.sub.i =the logic value of a signal positioned in the i digit order involved in a multiplicand X, and PA1 X.sub.i-1 =the logic value of a signal positioned in the X.sub.i-1 digit order involved in a multiplicand X, and PA1 .sym. denotes an exclusive logical sum, and .multidot. represents a logical product.
Formula (1) may be converted into following formula (2) ##EQU1##
FIG. 1 represents a logic circuit in the form of a logically symbolized diagram, which operates according to theoretical formula (2).
Reference numerals 11 to 13 given in FIG. 1 each denote a two-input NAND gate, and reference numeral 14, also in FIG. 1, represents a two-input exclusive OR gate. Signals QX and X.sub.i are input to the input terminals of NAND gate 11. Signals Q2X and X.sub.i-1 are input to the input terminals of NAND gate 12. Output signals of NAND gates 11 and 12 are input to input terminals of NAND gate 13. An output signal of NAND gate 13 is input to one input terminal of exclusive OR gate 14. Signal N is input to the other input terminal of exclusive OR gate 14. OR gate 14 outputs Booth-converted signal QB.
FIG. 2 is a diagram of the logic circuit of FIG. 1.
Referring to FIG. 2, portions therein which correspond to those of FIG. 1 are denoted by the same reference numerals.
NAND gate 11 is formed of P channel type MOS transistors 15, 16 and N channel type MOS transistors 17, 18. NAND gate 12 is composed of P channel type MOS transistors 19, 20 and N channel type MOS transistors 21, 22. NAND gate 13 is composed of P channel type MOS transistors 23, 24 and N channel type MOS transistors 25, 26.
Exclusive OR gate 14 comprises P channel type MOS transistors 27 to 29, and N channel type MOS transistors 30 to 32.
NAND gate 11 receives signals QX, X.sub.i. NAND gate 12 is supplied with signals Q2X, X.sub.i-1. Outputs from NAND gates 11, 12 are delivered to NAND gate 13. An output from NAND gate 13 and signal N are supplied to exclusive OR gate 14. Booth-converted output QB is obtained from exclusive OR gate 14.
The operation of the Booth's conversion circuit shown in FIG. 2 will now be described.
Now, let it be assumed that signals QX, X.sub.i have a high level ("H"). In this case, MOS (metal oxide semiconductor) transistors 15, 16 are rendered nonconductive, whereas MOS transistors 17, 18 are rendered conductive. As a result, the drain potential of MOS transistor 17 falls to ground potential (low potential). In other words, a low ("L") level signal is output from NAND gate 11.
When signal X.sub.i has low ("L") level and QX has high ("H") level, MOS transistors 15, 17 are rendered conductive, while MOS transistors 16, 18 are rendered nonconductive. Consequently, the source potential of MOS transistor 17 is allowed to float because of the nonconductive state of MOS transistor 18. The drain potential of MOS transistor 15 is raised to high level, i.e., high power source potential V.sub.DD. As a result, an output signal from NAND gate 11 has high ("H") level.
When signal QX has low ("L") level and signal X.sub.i has high ("H") level, MOS transistors 16, 18 are rendered conductive, whereas MOS transistors 15, 17 are rendered nonconductive. The drain potential of MOS transistor 18 remains floating because of the nonconductive condition of MOS transistor 17. The drain potential of MOS transistor 16 holds V.sub.DD potential, in which case an output signal from NAND gate 11 has a high potential.
When signals QX, X.sub.i both have low ("L") level, MOS transistors 15, 16 are rendered conductive, and MOS transistors 17, 18 are rendered nonconductive. As a result, the drain potential of MOS transistors 15, 16 is raised to V.sub.DD potential, and an output from NAND gate 11 has high level.
As is mentioned above, NAND gate 11 emits an output having low ("L") level when two input signals have high ("H") level, and outputs a signal having high ("H") level, in other cases.
NAND gates 12, 13 are substantially the same in their structure and operation.
Now, let it be assumed that signals Q2X, X.sub.i-1 have high level ("H"). In this case, MOS transistors 19, 20 are rendered nonconductive, whereas MOS transistors 21, 22 are rendered conductive. As a result, the drain potential of MOS transistor 21 falls to ground potential (low potential). In other words, a low ("L") level signal is output from NAND gate 12.
When signal X.sub.i-1 has low ("L") level and Q2X has high ("H") level, MOS transistors 19, 21 are rendered conductive, while MOS transistors 20, 22 are rendered nonconductive. Consequently, the source potential of MOS transistor 21 is allowed to float because of the nonconductive state of MOS transistor 22. The drain potential of MOS transistor 19 is raised to high level, i.e., high power source potential V.sub.DD. As a result, an output signal from NAND gate 12 has high ("H") level.
When signal Q2X has low ("L") level, and signal X.sub.i-1 has high ("H") level, MOS transistors 20, 22 are rendered conductive, whereas MOS transistors 19, 21 are rendered nonconductive. The drain potential of MOS transistor 22 retains floating because of the nonconductive condition of MOS transistor 21. The drain potential of MOS transistor 20 holes V.sub.DD potential, in which case, an output signal from NAND gate 12 has a high potential.
When signals Q2X, X.sub.i-1 both have low ("L") level, MOS transistors 19, 20 are rendered conductive, and MOS transistors 21, 22 are rendered nonconductive. As a result, the drain potential of MOS transistors 19, 20 is raised to V.sub.DD potential, and an output from NAND gate 12 has high level.
Now, let it be assumed that signals output from NAND gates 11, 12 have high level ("H"). In this case, MOS transistors 23, 24 are rendered nonconductive, whereas MOS transistors 25, 26 are rendered conductive. As a result, the drain potential of MOS transistor 25 falls to ground potential (low potential). In other words, a low ("L") level signal is output from NAND gate 13.
When the output signal of NAND gate 11 has low ("L") level and the output signal of NAND gate 12 has high ("H") level, MOS transistors 23, 25 are rendered conductive, while MOS transistors 24, 26 are rendered nonconductive. Consequently, the source potential of MOS transistor 25 is allowed to float because of the nonconductive state of MOS transistor 26. The drain potential of MOS transistor 23 is raised to high level, i.e., high potential V.sub.DD. As a result, an output signal from NAND gate 13 has high ("H") level.
When the output signal of NAND gate 11 has low ("L") level, and the output signal of NAND gate 12 has high ("H") level, MOS transistors 24, 26 are rendered conductive, whereas MOS transistors 23, 25 are rendered nonconductive. The drain potential of MOS transistor 26 retains floating because of the nonconductive condition of MOS transistor 25. The drain potential of MOS transistor 24 holds V.sub.DD potential, in which case, an output signal from NAND gate 13 has a high potential.
When the output signals of NAND gates 11, 12 both have low ("L") level, MOS transistors 23, 24 are rendered conductive, and MOS transistors 25, 26 are rendered nonconductive. As a result, the drain potential of MOS transistors 23, 24 is raised to V.sub.DD potential, and an output from NAND gate 13 has high level.
When an output from NAND gate 13 and signal N both have high ("H") level, MOS transistors 30, 31 are rendered conductive, and MOS transistors 27-29 are rendered noncon-ductive. The drain potential of MOS transistor 30 is reduced to the ground potential. The source of MOS transistor 31 and the gate of MOS transistor 32 are grounded via MOS transistor 30, and have low "L" level. As a result, MOS transistor 32 is rendered nonconductive, and the drain of MOS transistor 31 is connected to the ground potential. Therefore, exclusive OR gate 14 emits output signal QB having low ("L") level.
When, on the other hand, an output signal from NAND gate 13 and signal N both have low ("L") level, MOS transistors 27-29 are rendered conductive and MOS transistors 30-31 are rendered nonconductive. As a result, the drain potential of MOS transistor 27 is raised to high potential V.sub.DD, and the high ("H") level signal is supplied to the source of MOS transistor 31 and the gate of MOS transistor 32. When MOS transistor 32 is rendered conductive upon receipt of the high ("H") level signal, the source of MOS transistor 32 is reduced to low ("L") level. The drain of transistor 32 also falls to low ("L") level. The drain potential of MOS transistor 29 is also reduced to low ("L") level because the source of MOS transistor 29 has low ("L") level. Since the drain potential of MOS transistors 29, 32 falls to low ("L") level, an output signal QB from exclusive OR gate 14 has low ("L") level.
When an output signal from NAND gate 13 has high ("H") level, and signal N has low ("L") level, MOS transistors 30, 28 are rendered conductive, and MOS transistors 27, 29, 31 are rendered nonconductive. As a result, the drain potential of MOS transistor 30 falls to ground level. The gate potential of MOS transistor 32 falls to low ("L") level, causing MOS transistor 32 to be rendered nonconductive. On the other hand, the drain potential of MOS transistor 28 has high ("H") level, because the source potential of MOS transistor 28 has high ("H") level and the gate potential has low ("L") level.
As a result, an output signal QB from exclusive OR gate 14 has high ("H") level.
When an output signal from NAND gate 13 has low ("L") level and signal N has high ("H") level, MOS transistors 27, 29, 31 are rendered conductive, and MOS transistors 30, 28 are rendered nonconductive. When rendered conductive, MOS transistor 27 has its drain potential raised to high ("H") level. MOS transistor 32 is rendered conductive, because its gate is supplied with the high ("H") level signal from the drain of MOS transistor 27.
Since, on the other hand, the sources of transistors 29, 32 are supplied with high level ("H") signal, the drain potentials of MOS transistors 29, 32 have high ("H") level.
Consequently, output signal QB from exclusive OR gate 14 has high ("H") level.
As can be clearly understood from the above, only when it is supplied with two input signals having different voltage levels (namely, one input signal having high ("H") level and the other signal having low ("L") level), does exclusive OR gate 14 output a high ("H") level signal. When both input signals have the same voltage level (namely, both input signals have either high ("H") or low ("L") level), exclusive OR gate 14 issues a low ("L") level signal, thereby acting as an exclusive logical sum circuit.
NAND gates 11 to 13 and exclusive OR gate 14 cooperate to perform Booth's conversion.
However, since, in the conventional Booth's conversion circuit, as can be seen from FIGS. 1 and 2, an output signal is emitted via three logic circuit stages (a stage of NOR gates 11, 12, a stage of NOR gate 13, and a stage of exclusive OR circuit 14), a time delay corresponding to the total of the time periods spent in the three stages occurs before a Booth-converted output is produced, thus rendering the conventional Booth's conversion circuit unsuitable for high-speed operation. Since four logic circuits, i.e., 11, 12, 13, and 14 are involved, the conventional Booth's conversion circuit involves a large circuit system, occupying a considerable proportion of an integrated circuit chip. In particular, when Booth's algorithm is applied, the multiplier circuit has to be provided with numerous Booth's conversion circuits, with the result that the multiplier device occupies a large area on the semiconductor chip.
This invention has been accomplished in view of the above-mentioned circumstances, and is intended to provide a Booth's conversion circuit which ensures a high-speed operation and occupies a small space.
According to the invention, an improved Booth's conversion circuit is provided, which comprises:
a first switch circuit, which is supplied at one end with signal X.sub.i of a logic level positioned in the i digit order of a multiplicand X, and which is rendered conductive or nonconductive according to the logic level of signal QX of logic 1 or logic 0;
a second switch circuit, which is supplied at one end with signal X.sub.i-1 of a logic level positioned in the i-1 digit order of the multiplicand X, and which is connected at the other end to the opposite end of the first switch circuit, and is rendered conductive or nonconductive according to the logic level of signal Q2X of logic 1 or logic 0;
first and second transistors which are connected in series between the junction of the other ends of the first and second switch circuits and a reference potential, and which are rendered conductive or nonconductive according to the logic levels of signals QX, Q2X; and
an exclusive logic sum circuit which is connected at one end to the junction of the first and second switch circuits, and at the other end to a signal of logic 1 or logic 0.
In the Booth's conversion circuit embodying the present invention, the first and second transistors are rendered conductive or nonconductive in an inverse relationship with the first and second switch circuits. The junction of the output terminals of the first and second switch circuits has the same logic level as an output from NAND gate 13 shown in FIG. 1. Therefore, the number of elements and gates can be greatly reduced, thereby enabling the Booth's conversion circuit according to the present invention to be operated at high speed and to occupy a much smaller space than the conventional Booth's conversion circuit.